// https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 后序遍历递归计算二叉树直径（最长路径）
// 2. 直径定义：任意两节点间最长路径，可能不经过根节点
// 3. 递归返回当前子树深度，同时更新全局最大直径
// 4. 当前节点直径 = 左子树深度 + 右子树深度
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int ret = 0;

    int diameterOfBinaryTree(TreeNode* root) 
    {
        ret = 0;
        recur(root);
        return ret;
    }

    int recur(TreeNode* root)
    {
        int leftDepth = 0, rightDepth = 0;
        if (root->left)
            leftDepth = recur(root->left) + 1;
        if (root->right)
            rightDepth = recur(root->right) + 1;

        ret = max(ret, leftDepth + rightDepth);

        return max(leftDepth, rightDepth);
    }
};

int main()
{
    vector<string> nodes1 = {"1","2","3","4","5"};
    vector<string> nodes2 = {"1","2"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    cout << sol.diameterOfBinaryTree(root1) << endl;
    cout << sol.diameterOfBinaryTree(root2) << endl;

    return 0;
}